import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;

/**
 * 有效括号
 */
public class GenerateParenthesis {
    public static void  solution(int n ,List<String> result,String str,int left,int right){
        if (right > left){
            return;
        }
       if (left == n && right == n){
           result.add(str);
           return;
       }
       //left
         if (left < n){
             solution(n,result,str+"(",left+1,right);
         }
        // right
        if (right < left){
            solution(n,result,str+")" ,left,right+1);
        }
    }

    public static void main(String[] args) {
      List<String> res = new ArrayList<>();
      int n = 4;
        solution(n,res,"",0,0);
        res.forEach(x->{
            System.out.println(x);
        });
    }
}
